package 头条;

public class 头条机试2压缩空间的dp {
    public static void main(String[] args) {
        int[] a = {6, 3, 1};
        func(a);
    }

    //时间O(n^2) 空间O(n)
    private static void func(int[] a) {
        int[] min = new int[a.length];
        int[] sum = new int[a.length];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                if (i == j) {
                    min[j] = a[i];
                    sum[j] = a[i];
                    res = Math.max(res, min[j] * sum[j]);
                } else {
                    min[j] = Math.min(min[j - 1], a[j]);
                    sum[j] = sum[j - 1] + a[j];
                    res = Math.max(res, min[j] * sum[j]);
                }
            }
        }
        System.out.println(res);
    }
}
